Compilers are programs that translate computer programs written in source languages, such as FORTRAN, Pascal, C, and C++, into equivalent compiled programs consisting of assembly-language instructions or machine-code instructions. Compilers generally perform this translation in a series of distinct steps or phases. Initial phases perform lexical analysis, syntactic analysis, and semantic analysis, generating an intermediate-level translation that includes intermediate-code instructions. Later phases perform various optimizations to produce the final assembly-language or machine-code program. In certain optimization phases, a particular form of intermediate-level code, called static-single-assignment ("SSA") form code, facilitates and simplifies certain types of optimizations. In SSA-form code, each variable, or virtual register, is defined only once. At points in the SSA-form code where branches coalesce, phi instructions ("100 -instructions") are inserted to abstractly coalesce the definitions of a set of virtual registers from various incoming branches. A .phi.-instruction formally assigns an additional virtual register to the value of the corresponding virtual register defined in the particular program branch that is taken, during execution of the program, to arrive at the point where the various branches coalesce. In a later phase, the SSA-form intermediate-level code is transformed back to a non-SSA-form intermediate-level code by removing the .phi.-instructions and substituting, throughout the intermediate-level code, a single virtual register for the set of virtual registers coalesced by each .phi.-instruction. However, the transition from SSA-form intermediate-level code back to non-SSA-form intermediate-level code may be complicated as a result of intervening optimizations, including code motion and copy elimination. Because of these intervening optimizations, certain types of interferences between sets of variables coalesced by different .phi.-instructions may be produced. These interferences need to be detected and removed prior to the transition from SSA-form intermediate-level code back to non-SSA-form intermediate-level code.
Various algorithms have been proposed for detecting and removing interferences between the variables coalesced by .phi.-instructions of optimized SSA-form intermediate-level code. In particular, techniques for identifying and removing .phi.-instruction interferences are described in the following two references: (1) P. Briggs, T. Harvey, and Taylor Simpson, Static single assignment construction, Version 1.0, Technical Report, Rice University, July 1995; and (2) R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck, Efficiently computing status single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems, 13(4):451-490, October 1991. A detailed discussion of the theory and implementation of compilers can be found in a number of textbooks, including: Compilers: Principals, Techniques, and Tools, Aho, Sethi, and Ullman, Addison-Wesley Publishing Company, 1988; and Advanced Compiler Design & Implementation, Muchnick, Morgan Kaufmann Publishers, 1997. However, the currently-available algorithms are deficient in various aspects. They employ control flow graph representations and interference graphs, but do so by identifying and including algorithms for a number of different structural properties of the control flow graphs and interference graphs. This "special casing" approach suffers the disadvantage that, because there are potentially infinitely many different structural properties of control flow graphs and interference graphs that might require special-case algorithms, a "special case" approach cannot be proven to be correct for all control flow graphs and interference graphs that might arise in SSA-form intermediate-level code. Another disadvantage of currently-available algorithms is that they need to consider intermediate-level code instructions and traverse the control flow and interference graphs in certain predefined orders. This ordering requirement greatly complicates the algorithms. Finally, the currently-available algorithms remove .phi.-instruction interferences by introducing copy instructions, but end up inserting more copy instructions into the intermediate-level code than are strictly required to remove the .phi.-instruction interferences. These unnecessary copy instructions increase both the time required for execution and the size of the final assembly-language or machine-code program produced by the compiler.
A need has therefore been recognized in the area of compiler optimization for an improved method for eliminating .phi.-instruction interferences and for eliminating redundant copy instructions from SSA-form intermediate-level code. This improved method should provide a uniform framework that does not require any "special casing" approaches. The improved method should not impose any requirements either for traversing control flow graphs and interference graphs or for considering .phi.-instructions within the intermediate-level SSA-form code in particular orders. The improved method should not insert large numbers of redundant and unnecessary copy instructions into the SSA-form intermediate-level code to remove the interferences between .phi.-instructions.